package com.liunian.test;

public class LongestPalindrome {

	public String longestPalindrome1(String s) {
		char[] chars = s.toCharArray();
		char[] newChars = preprocess(chars);
		int center = 0;
		int right = 0;
		int[] res = new int[newChars.length];
		for (int i = 1; i < newChars.length - 1; i++) {
			int i_mirror = 2 * center - i;
			if (i < right) {
				res[i] = Math.min(right - i, res[i_mirror]);
			}
			while (newChars[i + 1 + res[i]] == newChars[i - 1 - res[i]]) {
				res[i]++;
			}
			if (i + res[i] > right) {
				right = i + res[i];
				center = i;
			}
		}
		int index = 0;
		int len = 0;
		for (int i = 0; i < newChars.length; i++) {
			if (res[i] > len) {
				len = res[i];
				index = i;
			}
		}
		int left = (index - len) / 2;
		return new String(chars, left, len);
	}

	private char[] preprocess(char[] chars) {
		char[] newChars = new char[2 * chars.length + 3];
		newChars[0] = '$';
		newChars[newChars.length - 1] = '^';
		newChars[newChars.length - 2] = '#';
		for (int i = 0; i < chars.length; i++) {
			newChars[2 * i + 1] = '#';
			newChars[2 * (i + 1)] = chars[i];
		}
		return newChars;
	}

	public static void main(String[] args) {
		LongestPalindrome longestPalindrome = new LongestPalindrome();
		System.out.println(longestPalindrome.longestPalindrome("babad"));
	}

	public String longestPalindrome(String s) {
		char[] chars = s.toCharArray();
		int maxLen = 1;
		int left = 0;
		for (int i = 0; i < s.length(); i++) {
			int len1 = getLen(chars, i, i);
			int len2 = getLen(chars, i, i + 1);
			int len = Math.max(len1, len2);
			if (len > maxLen) {
				maxLen = len;
				left = i - (len - 1) / 2;
			}
		}
		return new String(chars, left, maxLen);
	}

	private int getLen(char[] chars, int left, int right) {
		while (left >= 0 && right < chars.length && chars[left] == chars[right]) {
			left--;
			right++;
		}
		return right - left - 1;
	}

}
